Field of the Invention
The present invention relates to an information processing unit and an information processing method. Particularly, the invention is suited for use in an information processing unit that performs a ground-state search of an Ising model.
Description of Related Art
The Ising model is a model of statistical dynamics to explain behaviors of a magnetic substance. The Ising model is defined by spins having two values, that is, +1/−1 (or 0/1 or up/down), an interaction coefficient indicative of an interaction between the spins, and an external magnetic field coefficient for each spin.
Energy of the Ising model at the relevant time can be calculated from a spin alignment, the interaction coefficient, and the external magnetic field coefficient which are defined. An energy function of the Ising model can be generally represented by the following expression.
[Math. 1]
                              E          ⁡                      (            s            )                          =                              -                                          ∑                                  i                  <                  j                                            ⁢                                                J                                      i                    ,                    j                                                  ⁢                                  σ                  i                                ⁢                                  σ                  j                                                              -                                    ∑              i                        ⁢                                          h                i                            ⁢                              σ                i                                                                        (        1        )            
Incidentally, σi and σj represent i-th and j-th spin values, respectively; Ji, j represents the interaction coefficient between the i-th and j-th spins; hi represents the external magnetic field coefficient for the i-th spin; and σ represents the spin alignment.
A first term of Expression (1) is to calculate energy attributable to the interaction between the spins. Generally, the Ising model is expressed as an undirected graph and does not distinguish between an interaction from the i-th spin to the j-th spin or an interaction from the j-th spin to the i-th spin. Therefore, the first term calculates the influence of the interaction coefficient with respect to a combination of σi and σj that satisfy i<j. Also, a second term is to calculate energy attributable to the external magnetic field for each spin.
A ground-state search of the Ising model is an optimization problem to find a spin alignment that minimizes the energy function of the Ising model. It is known that when the range of the interaction coefficient and the external magnetic field coefficient is not limited, finding the ground state of the Ising model whose topology becomes a nonplanar graph is an NP-hard problem.
The ground-state search of the Ising model is used not only to explain behaviors of a magnetic substance which is originally a target of the Ising model, but also for various uses. This can be because the Ising model is the simplest model based on interactions and also has the capability to express various phenomena attributable to interactions. For example, Japanese Patent Application Laid-Open (Kokai) Publication No. 2012-217518 discloses a method for estimating the degree of stress in a group such as a workplace organization by using the ground-state search of the Ising model.
Furthermore, the ground-state search of the Ising model also deals with a maximum cut problem known as an NP-hard graph problem. Such a graph problem is widely applicable to, for example, community detection in social networks and segmentation for image processing. Therefore, any solver that performs the ground-state search of the Ising model can be applied to such various problems.
Since finding the ground state of the Ising model is an NP-hard problem as described above, solving the problem with von Neumann computers is difficult in terms of calculation time. While an algorithm that introduces heuristics to increase the speed is suggested, there is suggested a method of finding the ground state of the Ising model at high speeds, without using the von Neumann computers, by calculation that utilizes physical phenomena more directly, that is, by using analogue computers. For example, there is an apparatus described in WO2012/118064 as an example of the above-described apparatus.
Assuming hardware having the configuration that corresponds to Ising models one-on-one, types of coefficient values which the hardware can retain are limited.
The types of coefficient values represent individual coefficients that can be used specifically. The hardware cannot handle arbitrary real numbers with unlimitedly high precision. In many cases, values which can be directly supported by the hardware are integer numbers which are discrete values. Moreover, when the hardware supports real numbers as fixed point numbers and floating point numbers, their precision is actually limited and can be considered as discrete values. Furthermore, in any of the cases, it is physically difficult to prepare values which can fully cover the range, so that it is assumed that available coefficient values will be sparse.
Even with the hardware on which coefficients are mounted in an analogue manner, actually available coefficients are limited to a limited number of discrete values due to influences of a dynamic range or noise level of the hardware. Furthermore, there is a possibility that the size of the available coefficients may not be maintained to be uniform depending on the configuration of the hardware and ununiform coefficients may be provided. Therefore, specifically what type of values is available becomes a problem and this is called the types of coefficients. Specifically speaking, some hardware supports five types of coefficients such as +2, +1, 0, −1, −2, and some hardware supports four types of coefficients such as +2, +0.5, 0, −2. Furthermore, coefficients that increase in units of tenfold such as +100, +10, +1, 0, −1, −10, −100 may sometimes be provided. In other words, the coefficients may not be simply discrete values with equal intervals between adjacent values and the intervals may vary.
Such hardware may possibly use storage devices such as memory cells to retain the coefficients and use functional units or amplifiers to cause influences of the size of the coefficients. Accordingly, the types of the coefficient values are restricted by, for example, the bit width of the memory cell and the functional unit and the dynamic range of the amplifier.
Furthermore, since it is generally necessary to deliberately control many hardware resources and irregularity at the time of manufacturing in order to expand the bit width and the dynamic range, this will result in an increase in an amount of materials and costs. From this point of view as well, while the configuration of the hardware which realizes arbitrary coefficients can be thought of theoretically, only certain limited types of coefficient values can provided realistically. As an example, it is assumed that such coefficients may be only two values of +1 and −1 or only three values of +1, 0, and −1.
Furthermore, even when a solver that performs a ground-state search of an Ising model is implemented using software, the types of the coefficient values that the solver can deal with are limited, in the same manner as in the case of the ground-state search of the Ising model by the hardware, due to restrictions attributable to, for example, data structures to retain the coefficients in a memory for a computer which executes the solver.
For example, |V| represents the number of spins (corresponding to the number of vertexes in a graph) in an Ising model; and |E| represents the average number of interaction coefficients that each spin has (corresponding to an average degree in a graph). Assuming that a memory that can be allocated to the solver is N bits and the bit width of an interaction coefficient is k bits, only a model that satisfies the following expression can be used.
[Math. 2](|V|×|E|×k)≤N  (2)
Particularly, if an attempt is made to expand the bit width k of the interaction coefficient, that is, to expand the types of the coefficient values, it is necessary to reduce the number of spins |V| or the topology of the Ising model (the average number of interaction coefficients |E| for each spin).
It is possible to make efforts to increase the memory amount N which can be allocated to the solver by, for example, preparing virtual storage on a computer platform where the solver is made to operate; however, even if the solver is realized by using the software, the fact remains that the types of the coefficient values which can be handled by the Ising model are still restricted by the hardware.
Consequently, although the ground-state search of the Ising model exhibits industrially useful applicability, the types of the coefficient values are limited by the restrictions of the hardware when implementing the solver which performs the ground-state search; and apparently, the problem is that types of Ising models which can be input to the solver are limited.
It should be noted that conventionally, in the field of combinatorial optimization problems in which von Neumann computers are used to perform such a search, the computational complexity explodes exponentially relative to the input size of a problem. So, types of values constituting the problem have rarely become a problem. Instead, the explosion of the computational complexity in the search processing after inputting the problem has been a controlling problem. Therefore, for example, a branch-and-bound method and heuristics to reduce the computational complexity by utilizing characteristics of the problem have been used as described in Japanese Patent Application Laid-Open (Kokai) Publication No. 2004-133802 and Japanese Patent Application Laid-Open (Kokai) Publication No. Hei 9-300180.
So, the types of the coefficient values which can be input to the solver were never a problem in the past in the first place, besides the computational complexity as mentioned above. However, as it has become possible to perform an NP-hard ground-state search of the Ising model at high speeds as in a case of the apparatus described in WO2012/118064, the computational complexity problem has been solved. Then, the above-described problem has arisen as a new problem.
The present invention was devised in consideration of the above-described circumstances and aims at suggesting an information processing unit and information processing method capable of performing a ground-state search of an Ising model having coefficients of arbitrary values regardless of restrictions on hardware or software.